/* 
 * 周教授讲授计算机算法课程，班上一共有72个学生。每一周，周教授都安排这些学生见一次面。
 * 有些周，周教授将72名学生分为每组8人，另外一些周，周教授将72名学生分为每组9人。
 * 只要两个学生被分在同一组，就算见一次面。周教授分组的原则是，在整个授课过程中，任意两
 * 个学生必须见一次面，且仅见一次面。问，周教授的课程需要安排多少周？周教授需要如何将这
 * 些学生分组？
 * 
 * 周教授有125名学生，将其分为25组，每组5名学生，周教授的课一共上31周。每一周，周教授
 * 让这些学生见一次面。如果算法课程结束时，任意两个学生恰好见了一次面，问，周教授如何分
 * 组？
 */

#include <stdio.h>
#include <assert.h>
#include <iostream>
#include <vector>
#include <set>
#include <time.h>

#define STUDENT_NUM      72
#define INIT_GROUP_SIZE   8
#define INIT_GROUP_NUM    9
#define GROUP_SIZE        9   

class Relation
{
private:
    int meeted[STUDENT_NUM][STUDENT_NUM] = {0};

public:
    Relation()
    {
        for (int i = 0; i < STUDENT_NUM; i++) {
            meeted[i][i] = 1;
        }
    }

    void print()
    {
        printf("Meeted:\n");
        for (int i = 0; i < STUDENT_NUM; i++) {
            for (int k = 0; k < STUDENT_NUM; k++)
                printf("%3d", meeted[i][k]);
            printf("\n");
        }
    }

    bool solved()
    {
        for (int i = 0; i < STUDENT_NUM; i++) {
            for (int k = 0; k < STUDENT_NUM; k++)
                if (!meeted[i][k]) return false;
        }
        return true;
    }

    bool is_meeted(int a, int b)
    {
        return meeted[a][b];
    }

    void meet(int a, int b)
    {
        meeted[a][b] = 1;
        meeted[b][a] = 1;
    }

    void unmeet(int a, int b)
    {
        meeted[a][b] = 0;
        meeted[b][a] = 0;
    }
};

Relation relation;
class Group;
std::vector<Group *> solution;
clock_t start, finish;

// 分组类
class Group
{
private:
    int  group_size;          // 分组大小
    int  group_num;           // 分组数
    int  student_num;         // 学员人数
    std::vector< int >            grouped;  // 学员i是否已经分组

public:
    std::vector< std::vector<int> >  groups;   // 学员分组方案
    Group(int num, int size)
    {
        // std::cout << "Enter new Group class." << std::endl;
        if (num % size != 0) {
            std::cout << "Invalid student num and group size!" << std::endl;
            assert(num % size == 0);
        }
        student_num = num;
        group_size  = size;
        group_num   = num / size;
        groups.resize(group_num);
        for (int i = 0; i < group_num; i++)
            groups[i].resize(group_size);
        grouped.resize(num);
    }

    void init()
    {
        int num = 0;
        for (int i = 0; i < group_num; i++) {
            for (int k = 0; k < group_size; k++) {
                groups[i][k] = num;
                num++;
            }
        }
    }

    void generate(Group* init, int dist)
    {
        for (int i = 0; i < group_num; i++) {
            int m = i;
            for (int k = 0; k <group_size; k++) {
                groups[i][k] = init->groups[k][m];
                m = (m + dist) % INIT_GROUP_SIZE;
            }
        }
    }

    void print_group(int id)
    {
        printf("Group[%d]:", id);
        for (int i = 0; i < group_size; i++)
            printf("%3d", groups[id][i]);
        printf("\n");
    }

    void print()
    {
        for (int i = 0; i < groups.size(); i++)
            print_group(i);
    }

    // 学员stud与group分组的成员是否见过面
    void refresh_meeted()
    {
        for (int i = 0; i < group_num; i++)
            for (int k = 0; k < group_size - 1; k++)
                for (int m = k + 1; m < group_size; m++) {
                    relation.meet(groups[i][k], groups[i][m]);
                }
    }

    bool meeted_group(int line, int colm, int stud)
    {
        for (int i = 0; i < colm; i++) {
            if (relation.is_meeted(groups[line][i], stud)) return true;
        }
        return false;
    }

    void divide(Group* init, int line, int colm)
    {
        // printf("init=%p, line=%d, colm=%d\n", init, line, colm);
        if (line >= group_num) {
            // 打印当前的解决方案
            for (int i = 0; i < solution.size(); i++) {
                printf("Week %d\n", i + 1);
                solution[i]->print();
                delete solution[i];
            }
            if (relation.solved()) {
                printf("Find solution.\n");
                exit(0);
            }
            printf("Enter new week divide...\n");
            Group* group = new Group(STUDENT_NUM, GROUP_SIZE);
            solution.push_back(group);
            group->divide(init, 0, 0);
            solution.pop_back();
            delete group;
            return;
        }
        if (colm >= group_size) {
            divide(init, line + 1, 0);
            return;
        }
        for (int i = 0; i < INIT_GROUP_SIZE; i++) {
            int stud = init->groups[colm][i];
            printf("colm=%d, i=%d, stud=%d, init=%d\n", colm, i, stud, init->groups[colm][i]);
            // init->print();
            if ((!grouped[stud]) && (!meeted_group(line, colm, stud))) {
                // 将学员stud分到第group分组
                grouped[stud] = true;
                groups[line][colm] = stud;
                // 将学员stud与本组学员置为已见面
                for (int k = 0; k < colm; k ++)
                    relation.meet(stud, groups[line][k]);
                
                // 尝试下一个学员分组
                divide(init, line, colm + 1);

                // 回溯时还原
                grouped[stud] = false;
                groups[line][colm] = 0;
                for (int k = 0; k < colm; k ++)
                    relation.unmeet(stud, groups[line][k]);
            }
        }
    }
};

int main()
{
    start = clock();
    
    // 生成原始分组
    Group* init = new Group(STUDENT_NUM, INIT_GROUP_SIZE);
    init->init();
    init->refresh_meeted();
    solution.push_back(init);

    // for (int i = 0; i < INIT_GROUP_SIZE; i++) {
    //     Group* group = new Group(STUDENT_NUM, GROUP_SIZE);
    //     group->generate(init, i);
    //     group->refresh_meeted();
    //     solution.push_back(group);
    // }

    // for (int i = 0; i < solution.size(); i++) {
    //     printf("Week %d\n", i + 1);
    //     solution[i]->print();
    //     delete solution[i];
    // }

    Group* group = new Group(STUDENT_NUM, GROUP_SIZE);
    solution.push_back(group);
    group->divide(init, 0, 0);
    solution.pop_back();
    delete group;

    delete init;
}